#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

#define MAX_VALUE 1000
class Solution {
    public:
    int coin_count (const vector<int>& nums, int amount) {

        // 定义一个数组dp，长度为amount+1;dp[i]表示的是达成i元所需要的最小硬币数;初始条件为dp[0]=0;
        int dp[amount + 1];
        for (size_t i = 0; i <= amount; i++) {
            if (i == 0) dp[i] == 0;
            else dp[i] == MAX_VALUE;
        }

        for (int coin : nums) {
            for (int i = coin; coin <= amount; i++) {
                if (dp[i - coin] != MAX_VALUE) {
                    dp[i] = min(dp[i], dp[i - coin] + 1);
                }
            }
        }

        return dp[amount] == MAX_VALUE? -1 : dp[amount];
    }
};